\chapter{文件恢复工具的实现}
本章将描述\yaffsrecover 的实现，包括各模块的实现、各模块交互的实现以及人机界面的实现。

\section{开发环境}
\yaffsrecover 在Linux环境下开发，依赖\texttt{libc}以及YAFFS2的部分源代码（\texttt
{GIT修订}\texttt{d43e901b}）。OOB信息提 取工具使用了Linux系统调用\texttt{ioctl}. 工
程使用Makefile指导编译，在\texttt{GCC 4.6.3}下编译通过；在Linux（内核版本3.3.4-3）下运
行。

\section{源文件清单}

\yaffsrecover 利用了部分YAFFS2的源文件（主要是头文件），因此在源文件目录下，需要创建一个
到YAFFS2源文件目录的链接。在编译时，\texttt{make}会自动将所需的文件链接到源文件目录下。

下面分别列出\yaffsrecover 自己的源文件清单和从YAFFS2中提取的源文件清单：

%TODO: GUI files?
\begin{center}
\captionof{table}{\yaffsrecover 源文件及描述}
\begin{tabular}{lll}
\hline
模块 & 文件 & 描述 \\
\hline
NAND模拟层 & \verb|nand.c nand.h| & NAND镜像文件解析 \\
 & \verb|mtd_sim.c mtd_sim.h mtd.h|& NAND设备模拟 \\
Chunk解析器 & \verb|yaffs_read.c yaffs_read.h| & Chunk解析器 \\
文件chunk组织索引 & \verb|file_list_tree.c| & 文件chunk组织索引 \\
 & \verb|file_list_tree.h| & \\
 & \verb|tree.h| & BSD 红黑树实现  \\
文件恢复算法 & \verb|file_recover.c file_recover.h| & 文件恢复算法 \\
OOB信息提取工具 & \verb|get_ooblayout.c| & OOB信息提取工具 \\
人机接口 & \verb|yaffs2recover.c| & 程序入口以及人机接口 \\
\hline
\end{tabular}
\end{center}

\begin{center}
\captionof{table}{\yaffsrecover 引用的YAFFS2源文件及描述}
\captionof*{table}{带*号的项目仅为编译依赖，工程中并未引用其中内容}
\begin{tabular}{ll}
\hline
文件 & 描述 \\
\hline
\verb|yaffs_ecc.c yaffs_ecc.h| & 软ECC检查*\\
\verb|yaffs_guts.h| & 数据结构定义、工具函数原型声明\\
\verb|yaffs_hweight.c yaffs_hweight.h| & 汉明距离计算*\\
\verb|yaffs_list.h| & YAFFS自带的链表实现\\
\verb|yaffs_packedtags2.c| & chunk元信息提取，chunk解析器\\
\verb|yaffs_packedtags2.h| \\
\verb|yaffs_trace.h| & Debug工具*\\
\verb|yaffs_yaffs2.h| & YAFFS2特有数据结构定义、工具函数声明\\
\verb|yportenv.h yutilsenv.h| & 操作系统相关的常数、函数原型声明*\\
\hline
\end{tabular}
\end{center}

\section{具体实现方案}
本节自底向上地介绍\yaffsrecover 的各个模块的实现方案。
\subsection{NAND模拟层}
本模块使用了论文\cite{Baiyi}的基于YAFFS1的文件恢复工具中的相关代码。

该模块由两层分组成：
\begin{itemize}
\item NAND镜像文件读取及解析
\item MTD设备描述
\end{itemize}
前一层实现的函数作为后一层MTD设备所使用的读、写接口。仅有MTD设备结构向\yaffsrecover 上层模块（chunk解析扫描）开放。

MTD设备由以下结构体定义（限于篇幅，仅列出向上下层模块需要使用的域）：
\begin{center}
\captionof{lstlisting}{MTD设备定义}
\begin{lstlisting}

struct mtd_info {
	...
	/* Total size of the MTD */
	unsigned int size;	 
	/* Block size */
	unsigned int erasesize; 
	/* Chunk size */
	unsigned int writesize;
	/* Amount of OOB data bytes per block */
	unsigned int oobsize; 
	/* Available OOB bytes per block */
	unsigned int oobavail;  
	/* OOB layout */
	struct nand_ecclayout *ecclayout; 
	/* Raw reading */
	int (*read) (struct mtd_info *mtd, loff_t from, unsigned int len,
		unsigned int *retlen, u_char *buf);
	/* Raw writing */	
	int (*write) (struct mtd_info *mtd, loff_t to, unsigned int len, 
		unsigned int *retlen, const u_char *buf);
	/* Read with OOB data */
	int (*read_oob) (struct mtd_info *mtd, loff_t from,
		struct mtd_oob_ops *ops);
	/* Write with OOB data */
	int (*write_oob) (struct mtd_info *mtd, loff_t to,
		struct mtd_oob_ops *ops);
	...	
};

\end{lstlisting}
\end{center}

此MTD设备结构由NAND镜像文件读取模块来初始化，其函数指针的指向关系如下：

\begin{center}
\captionof{table}{MTD设备中的函数指针指向的NAND读写函数}
\begin{tabular}{ll}
\hline
指针名 & 指向\verb|nand.c|中函数 \\
\hline
\verb|read| & \verb|nand_read| \\
\verb|write| & \verb|nand_write|\\
\verb|read_oob| & \verb|nand_read_oob| \\
\verb|write_oob| & \verb|nand_write_oob| \\
\hline
\end{tabular}
\end{center}

NAND镜像读写模块在初始化MTD设备后，将读取给定的NAND镜像文件进入内存，而其中实现的所有NAND读写相关的函数，均为内存读写操作。

本模块向上开放的接口是一个全局的已经初始化完毕的MTD设备的指针。
\subsection{Chunk解析器}
Chunk解析器要负责解析两种信息：
\begin{itemize}
\item chunk的元信息：进行位压缩后存放在OOB区域中。
\item 头chunk中包含的文件元信息：按照\verb|yaffs_obj_hdr|结构的定义存入chunk的数据区域。
\end{itemize}
这两个任务在YAFFS2的源文件中都有相应的代码实现，但是这些代码依赖于YAFFS2的运行时环境（YAFFS2运行时维护了一棵chunk树，在恢复工作中是不必要的）。我将这些代码进行了重写，使之
摆脱了上述依赖。

该模块向上开放的接口函数是\verb|yaffs_read.c: yaffs_read_chunk_with_tags|. 它调用MTD
设备的读取接口，读取一chunk并且将OOB区域中的元信息进行解压，同时返回chunk的数据部分和元信息部分。该
函数用到了YAFFS2自带的元信息解压函数（位于\verb|yaffs_packedtags2.c|）。

至于文件的元信息，只需利用在\verb|yaffs_guts.h|中定义的\verb|yaffs_obj_hdr|结构体，将chunk内容按该类型读取即可。

\subsection{文件chunk组织索引}
如图\ref{fig:chunk_tree}所示，在chunk被扫描、解析后，它们将以链表的形式组织在所属的对象之下，并且对象用平衡二叉树进行组织。

在实际实现中，\yaffsrecover 采用了YAFFS2提供的链表和经过一些修改的BSD操作系统中的红黑树
实现。避免使用Linux自带的上述数据结构实现的好处是保证了可移植性。

本模块中有两个主要对象：YAFFS对象和chunk。它们定义在\verb|file_list_tree.h|中，具体定义如
下：

其中\verb|file_chunk|结构体表示了文件chunk;\verb|file_chunk_list|表示YAFFS2对象。
\begin{center}
\begin{lstlisting}

struct file_chunk{
	/* the logical position on the NAND */
	int chunk_number; 
	/* the number of obj headers before this chunk */
	int num_headers_before; 
	/* meta data of a chunk */
	struct yaffs_ext_tags tags; 
	/* list sorted by chunk id */
	struct list_head list_entry; 
	/* 
	 * rb-tree is used to deduplicate 
	 * the chunk_id and sort the chunks 
	 *  by chunk_id 
	 */
	RB_ENTRY(file_trunk) rb_entry; 
};

struct file_chunk_list{
	/* yaffs object id */
	unsigned obj_id; 
	/* object type (dir / file) */
	enum yaffs_obj_type obj_type; 
	/* BSD rb-tree entry, indexed by obj_id */
	RB_ENTRY(file_trunk_list) rb_entry;  
	/* list of file chunks, 
	 * sorted by seq_number (chronically) */
	struct list_head chunk_list; 
	/* obj_id of parent directory, usually */
	struct file_trunk_list *parent_object; 
};
\end{lstlisting}
\captionof{lstlisting}{YAFFS2 object and file chunk}\label{lst:chunk}
\end{center}

注意到两个结构体中均包含\verb|struct list_head|类型，但它们代表的意义不同：前者中仅是双链
表的\verb|next, prev|指针，后者中则是链表的头。同样，两个结构体中均包含的\verb|rb_entry|
项也是提供给不同模块使用的。前者的是在文件恢复算法中用来表示集合K的红黑树的节点指针；后者的是
文件chunk组织索引用的红黑树的节点指针。

本模块向上层模块开放如下两个接口函数：
\begin{itemize}
\item \verb|build_file_list_tree|: 调用chunk解析器提供的接口，扫描NAND中的所有chunk，并
且按照写入的时间顺序排序。然后对于排序好的每个chunk，将它们链入其所属的对象的chunk链表中；若所属对
象不存在，则创建一个新的对象，并加入红黑树。最后，遍历此红黑树，将每个对象的父对象的指针存入
该对象的\verb|parent_object|中。
\item \verb|file_list_tree_iterate|: 遍历对象红黑树。该函数接受一个以对象节点为参数的
函数，在对红黑树进行中序遍历的时候对每个遍历到的节点调用这个函数。
\end{itemize}

\subsection{文件恢复算法}
文件恢复算法完全按照上一章算法\ref{alg:1}和算法\ref{alg:2}的描述进行实现。
\yaffsrecover 使用一棵以chunkID为key的红黑树来表示集合K；集合R并没有显式的结构对应，而
是直接向磁盘写入了已经恢复出的版本；集合F也没有显式的结构对应，而是对集合K进行遍历（即红黑树
的中序遍历），并且在chunkID间断，即文件中有全0的chunk时调用\verb|libc|中的\verb|fseek|函数
来跳过全0的区域。

本模块向上开放的接口函数是\verb|file_recover_iterate_tree|，该函数调用文件chunk索引提供
的遍历函数，逐个对象红黑树中的所有对象的每个版本进行恢复。

\subsection{命令行人机界面}
\yaffsrecover 有两种命令行界面，一种是参数式命令行，用于快速或批量执行
恢复命令或查看镜像文件信息；另一种是交互式命令行，它实现了一个简单的命令解析
器，使用户可以利用程序内建的命令来查看某个文件的具体信息。

\subsubsection{参数命令行}
\yaffsrecover 使用了GNU样式的长参数命令行，调用方法如下：
\begin{lstlisting}[language=bash]
yaffs2recover [options] NAND-image
Options: 
	-h	--help	show this help message 
			and quit
	-n	--dry-run	do not run recovery 
				(print info only)
	-m	--mtd-info	print NAND image info
	-c	--chunks-info	iterate all YAFFS2 chunks 
				and print info
	-i	--interactive=FIFO	interactive mode; 
					long argument needs 
					a pipe file
\end{lstlisting}

\subsubsection{交互式命令行}
使用参数\verb|-i|或\verb|--interactive=FIFO|进入交互式命令行。
其中\verb|FIFO|是一个Linux管道文件。利用管道，可以为\yaffsrecover
开发图形界面前端。

交互式命令行现有的命令即介绍如下：
\begin{center}
\begin{tabular}{ll}
\hline
命令语法 & 功能\\
\hline
\verb|help| & 显示命令帮助\\
\verb|exit| & 退出程序\\
\verb|recoverall| & 恢复镜像中的所有文件\\
\verb|listall| & 按objectID排序输出镜像中的所有文件\\
\verb|recover OBJID| & 恢复指定objectID的文件 \\
\verb|chunkinfo OBJID| & 列出指定objectID的文件的所有chunk的信息\\
\hline
\end{tabular}
\end{center}

程序根据是否使用管道作为命令输入，会采用不同的输出格式。如果不采用管道，则
输出以对用户友好的格式输出各种信息；否则，则忽略所有提示信息，并且将文件信息
和chunk信息以JSON的格式输出，方便前端进行解析。
%\subsubsection{图形界面人机接口}
%TBD
